长大后想做什么？做回小孩！

0%

LeetCode——将数组分成和相等的三个部分

发表于 更新于 分类于 Valine：
本文字数： 330

NO.1013 将数组分成和相等的三个部分 简单

8A3zR0.png

思路一：双指针法 一个数组能分成和相等的三部分，则这个数组元素总sum和必定是3的倍数，如不是则否定。

双指针头尾开始同时遍历，寻找最左部分和最右部分总和等于sum/3的位置，并且寻找过程中要给中间部分留有余地(中间部分至少是一个元素)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean canThreePartsEqualSum(int[] A) {
    //元素总和必须是3的倍数
    int sum=0;
    for (int i : A) {
        sum+=i;
    }
    if (sum%3!=0)return false;
    //双指针找和等于sum/3的左右部分
    int left=0,right=A.length-1,leftSum=A[0],rightSum=A[A.length-1];
    //+1给中间部分留有"余地"
    while (left+1<right){
        if (leftSum == sum / 3 && rightSum == sum / 3) {
            return true;
        }
        if (leftSum != sum / 3) {
            leftSum+=A[++left];
        }
        if (rightSum != sum / 3) {
            rightSum+=A[--right];
        }
    }
    return false;
}

时间复杂度：O(n)

思路二：计数器法 和思路一差不多，先判断元素总和是否满足条件。

顺序遍历，count计数器记录有多少部分的和等于sum/3。

如果count>=3，则true。为什么是>=？例如[1,-1,1,-1,1,-1,1,-1]，count==4这个数组依然符合要求。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public boolean canThreePartsEqualSum(int[] A) {
    //元素总和必须是3的倍数
    int sum = 0;
    for (int i : A) {
        sum += i;
    }
    if (sum % 3 != 0) return false;
    //顺序遍历找等于sum/3的部分
    int count = 0, partialSum = 0;
    for (int i : A) {
        partialSum += i;
        if (partialSum == sum/3) {
            partialSum=0;
            count++;
        }
    }
    return count>=3;
}

时间复杂度：O(n)

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github